// 提交链接 https://leetcode.cn/problems/edit-distance/submissions/562823013/
// 72. 编辑距离
// 完成日期： 2024.9.8
// c++ 动态规划枚举每一步的操作，选择最少操作步数

class Solution {
public:
    pair<int, bool> dp[505][505];
    int minDistance(string word1, string word2) {
        word1.insert(word1.begin(), ' ');
        word2.insert(word2.begin(), ' ');
        return dfs(word1.size() -1, word2.size() - 1, word1, word2);
    }
    int dfs(int pos1, int pos2, string& s1, string& s2)
    {
        if (!pos1 || !pos2) return abs(pos1 - pos2);
        if (dp[pos1][pos2].second) return dp[pos1][pos2].first;
        int n1 = dfs(pos1 - 1, pos2, s1, s2) + 1;
        int n2 = dfs(pos1, pos2 - 1, s1, s2) + 1;
        int n3 = dfs(pos1 - 1, pos2 - 1, s1, s2);
        if (s1[pos1] != s2[pos2]) n3 += 1;
        dp[pos1][pos2].second = 1;
        return dp[pos1][pos2].first = min(n1, min(n2, n3));
    }
};